import java.awt.*;
import java.text.*;

/**
 * @author base code by Chip Klostermeyer @
 *         http://www.unf.edu/~wkloster/3540/234tree.java modified by Team C
 *         2-3-4 Node implementation by Team C
 * 
 * @param <AnyType>
 *            type of element for the node
 */
public class Tree234<AnyType extends Comparable<? super AnyType>> implements
		TreeInf<AnyType> {

	private Node234<AnyType> root;
	// private int size;
	public static int rootX;

	public Tree234()
	{
		root = null;
		// size = 0;
	}

	public boolean search(AnyType key)
	{

		if (!isCleared())
		{
			Node234<AnyType> curNode = root;

			while (true)
			{
				if (curNode.findElement(key) == true)
					return true;
				else
					if (curNode.isLeaf())
						return false;
					else
						curNode = getNextChild(curNode, key);
			}
		}

		// Tree is empty
		return false;
	}

	public void delete(AnyType e)
	{
		root.delete(e);

		if (root.getNumElements() == 0 && root.getChild(0) != null)
		{
			root = root.getChild(0);
		} else
			if (root.getNumElements() == 0)
			{
				root = null;
			}
		// !!!Decrements size even, if a delete was not performed!!!
		// size--;
	}

	/**
	 * Calculate the average depth of all node elements in the tree
	 * 
	 * @return the average depth
	 */
	public double getAverageDepth()
	{
		if (!this.isCleared())
		{
			// Root depth = 0
			return (double) root.getTotalDepths(0) / getElementSize();
		}

		// Empty tree
		return 0.0;
	}

	/**
	 * Returns the size, height, and average element depth of the tree
	 * 
	 * @return a single line string containing all statistics
	 */
	public String toString()
	{
		StringBuffer tree_stats = new StringBuffer("Tree Statistics{");
		DecimalFormat fmt = new DecimalFormat("0.00");

		tree_stats.append(" Size(Nodes): ");
		tree_stats.append(this.getSize());
		tree_stats.append(" | Height: ");
		tree_stats.append(this.getHeight());
		tree_stats.append(" | Size(Keys): ");
		tree_stats.append(this.getElementSize());
		tree_stats.append(" | Avg. Depth: ");
		tree_stats.append(fmt.format(this.getAverageDepth()));
		tree_stats.append(" }");

		return tree_stats.toString();
	}

	public String inOrderTraversal()
	{
		if (!this.isCleared())
		{
			return root.inOrderTraversal();
		}

		return "{empty}";
	}

	/**
	 * 
	 * @return the center point of the root node
	 */
	public Point getLocation()
	{
		if (!isCleared())
		{
			return root.getCenter();
		}

		return null;
	}

	/**
	 * Sets center point of root node, which cascades changes to all child nodes
	 * 
	 * @param root_center
	 *            - the new center
	 */
	public void setLocation(Point root_center)
	{
		if (!isCleared())
		{
			root.setCenter(root_center);
		}
	}

	public void moveLocation(int dx, int dy)
	{
		if (!isCleared())
		{
			root.moveCenter(dx, dy);
		}
	}

	/**
	 * Draw the Tree recursively, beginning from the root
	 * 
	 * @param graph_2d
	 *            - the graphics area for drawing
	 */
	public void drawTree(Graphics2D graph_2d)
	{
		if (root != null && root.getCenter() != null)
		{
			root.drawNode(graph_2d);
		}
	}

	public void compressDrawWidth()
	{
		if (!this.isCleared())
		{
			root.compressSubTree();
			root.centerSubTree();
		}
	}

	public void setLeftEdgeGap(int gap_width)
	{
		// Node at left extent of tree
		Node234<AnyType> left_node = null;

		left_node = this.findMinimumNode();

		// Re-center tree when left extent is beyond edge of screen
		if (left_node != null && left_node.upperLeftX() < gap_width)
		{
			// Shift entire tree horizontally to the right
			this.moveLocation(gap_width - left_node.upperLeftX(), 0);
		}
	}

	/**
	 * Empties the tree, by setting the root to null
	 */
	public void clear()
	{
		root = null;
		// size = 0;
	}

	/**
	 * Determines if the tree is empty
	 * 
	 * @return whether the tree has a root node
	 */
	public boolean isCleared()
	{
		return root == null;
	}

	/**
	 * 
	 * @return the number of elements within the tree
	 */
	public int getElementSize()
	{
		// return size;
		if (!isCleared())
		{
			return root.getElementSize();
		}

		return 0;
	}

	/**
	 * 
	 * @return the number of nodes within the tree
	 */
	public int getSize()
	{
		if (!isCleared())
		{
			return root.getSize();
		}

		return 0;
	}

	/**
	 * Calculates the height of the tree. An empty tree has a height of (-1).
	 * 
	 * @return the height of the root node
	 */
	public int getHeight()
	{
		if (!isCleared())
		{
			return root.getHeight();
		}

		return -1;
	}

	/**
	 * Finds the right node, at the greatest depth, in this tree (i.e. - the
	 * node containing the largest elements)
	 * 
	 * @return the right-most node in the tree (null for an empty tree)
	 */
	public Node234<AnyType> findMaximumNode()
	{
		if (!isCleared())
		{
			return root.getMaximumNode();
		}

		return null;
	}

	/**
	 * Finds the left node, at the greatest depth, in this tree (i.e. - the node
	 * containing the smallest elements)
	 * 
	 * @return the left-most node in the tree (null for an empty tree)
	 */
	public Node234<AnyType> findMinimumNode()
	{
		if (!isCleared())
		{
			return root.getMinimumNode();
		}

		return null;
	}

	/**
	 * Inserts the given element into the tree
	 * 
	 * @param e
	 *            the element to be added to the tree
	 */
	public void insert(AnyType e) throws DuplicateItemException
	{

		// Performs the splits
		// in a top-down (root -----> leaf) fashion.

		if (search(e) != true)
		{
			Node234<AnyType> curNode = getRootInstance();
			DataElement234<AnyType> tempItem = new DataElement234<AnyType>(e);

			while (true)
			{
				if (curNode.isFull())
				{
					split(curNode);
					curNode = curNode.getParent();
					curNode = getNextChild(curNode, e);
				} else
					if (curNode.isLeaf())
					{
						break;
					} else
					{
						curNode = getNextChild(curNode, e);
					}
			}

			// size++;
			curNode.insertElement(tempItem);
		} else
		{
			throw new DuplicateItemException();
		}
	}

	/**
	 * Splits a node
	 * 
	 * @param thisNode
	 *            node to be split
	 */
	public void split(Node234<AnyType> thisNode)
	{
		// assumes node is full
		DataElement234<AnyType> itemB, itemC;
		Node234<AnyType> parent, child2, child3;
		int itemIndex;

		itemC = thisNode.removeItem();
		itemB = thisNode.removeItem();
		child2 = thisNode.disconnectChild(2);
		child3 = thisNode.disconnectChild(3);

		Node234<AnyType> newRight = new Node234<AnyType>();

		if (thisNode == root)
		{
			root = new Node234<AnyType>();
			parent = root;
			root.connectChild(0, thisNode);
		} else
			parent = thisNode.getParent();

		// deal with parent
		itemIndex = parent.insertElement(itemB);
		int n = parent.getNumElements();

		for (int j = n - 1; j > itemIndex; j--)
		{
			Node234<AnyType> temp = parent.disconnectChild(j);
			parent.connectChild(j + 1, temp);
		}

		parent.connectChild(itemIndex + 1, newRight);

		// deal with newRight
		newRight.insertElement(itemC); // item C to newRight
		newRight.connectChild(0, child2); // connect to 0 and 1
		newRight.connectChild(1, child3); // on newRight
	}

	/**
	 * gets the next child of a node
	 * 
	 * @param theNode
	 *            Node who's next child needs to be found
	 * @param theValue
	 * @return node that is the next child
	 */
	public Node234<AnyType> getNextChild(Node234<AnyType> theNode,
			AnyType theValue)
	{

		// Should be able to do this w/o a loop, since we should know
		// index of correct child already

		int j;

		// assumes node is not empty, not full, not a leaf
		int numItems = theNode.getNumElements();

		for (j = 0; j < numItems; j++)
		{
			if (theValue.compareTo(theNode.getElement(j).getKey()) < 0)
				return theNode.getChild(j);
		}

		return theNode.getChild(j);
	}

	public void displayTreeConsole()
	{
		if (isCleared())
		{
			System.out.println("{Empty}");
		} else
		{
			recDisplayTree(root, 0, 0);
		}

		// Output tree stats (toString)
		System.out.println(this);
	}

	/**
	 * Returns a non-null node for the tree root.
	 * 
	 * @return the root node
	 */
	private Node234<AnyType> getRootInstance()
	{
		if (isCleared())
		{
			root = new Node234<AnyType>();
		}

		return root;
	}

	private void recDisplayTree(Node234<AnyType> thisNode, int level,
			int childNumber)
	{
		System.out.print("level=" + level + " child=" + childNumber + " ");
		thisNode.displayNodeConsole();

		// call ourselves for each child of this node
		int numItems = thisNode.getNumElements();
		for (int j = 0; j < numItems + 1; j++)
		{
			Node234<AnyType> nextNode = thisNode.getChild(j);
			if (nextNode != null)
				recDisplayTree(nextNode, level + 1, j);
			else
				return;
		}
	}

	/**
	 * @author Simeon Gbolo This method tells all the nodes in the tree to
	 *         update them selves according to the given delta time - Helper
	 *         method that calls the private method
	 * @param deltaTime
	 */
	public void update(float deltaTime)
	{
		if (root != null)
		{

			update(root, deltaTime, 0, 0);

		}

	}

	/**
	 * @author Simeon Gbolo This method recursively tells the node to advance,
	 *         and then tells the node have it's dataElements update themselves
	 * @param thisNode
	 * @param deltaTime
	 * @param level
	 * @param childNumber
	 */
	private void update(Node234<AnyType> thisNode, float deltaTime, int level,
			int childNumber)
	{

		// this node will advance with a given delta time
		thisNode.advance(deltaTime);
		// now call updateMembers to udate the members
		thisNode.updateMembers(deltaTime);

		// call ourselves for each child of this node
		int numItems = thisNode.getNumElements();
		for (int j = 0; j < numItems + 1; j++)
		{
			Node234<AnyType> nextNode = thisNode.getChild(j);
			if (nextNode != null)
				update(nextNode, deltaTime, level + 1, j);
			else
				return;
		}

	}

	/**
	 * @author Simeon Gbolo This helper method tells the tree to recalculate all
	 *         positions/destinations starting at the root method and should
	 *         only be called if a new node has been inserted or deleted
	 */
	public void reCalculateDestinations()
	{
		if (root != null)
		{

			root.calculateDestination();
			rootX = (int) root.getCenter().getX();
		}

	}

	public void drawStates(Graphics2D g2)
	{
		if (root != null)
		{
			drawStates(g2, root);

		}
	}

	/**
	 * This method does the drawing of every node after each step in the
	 * animation and is called constantly (after repaint())
	 * 
	 * @param g2
	 * @param thisNode
	 */
	private void drawStates(Graphics2D g2, Node234<AnyType> thisNode)
	{

		g2.setColor(Color.GRAY.darker());
		g2.setStroke(new BasicStroke(3.2f));
		if (thisNode.getCenter() != null)
		{

			int rect_radius = thisNode.getDrawHeight() / 4;
			int thisNodeX = thisNode.getCurrentX();
			int thisNodeY = thisNode.getCurrentY();
			// Node border
			g2.drawRoundRect(thisNodeX, thisNodeY, thisNode.getDrawWidth(),
					thisNode.getDrawHeight(), rect_radius, rect_radius);
			// draw empty circles
			g2.setColor(Color.black.darker());

			g2.drawOval(thisNodeX, thisNodeY, 20, 20);
			g2.drawOval(thisNodeX + 20, thisNodeY, 20, 20);
			g2.drawOval(thisNodeX + 20 * 2, thisNodeY, 20, 20);

			for (int i = 0; i < thisNode.getElementArray().length; i++)
			{
				if (thisNode.getElement(i) != null)
				{

					int x = thisNode.getElement(i).getX();
					int y = thisNode.getElement(i).getY();
					int diameter = thisNode.getElement(i).getDrawDiameter();

					if (thisNode.getElement(i).isFound())
					{
						g2.setColor(Color.yellow);
						g2.fillOval(x, y, diameter - 1, diameter - 1);

					} else
					{
						g2.setColor(Color.green.darker());
						g2.fillOval(x + 1, y + 1, diameter - 1, diameter - 1);

					}

					if (thisNode.getElement(i).getKey() != null)
					{
						String s = thisNode.getElement(i).getKey().toString();

						if (thisNode.getElement(i).state == DataElement234.DataElement234State.paused)
						{
							x = thisNode.getElement(i).dataCenterX() + 1;
							y = thisNode.getElement(i).dataCenterY();
						} else
						{

							if (Integer.parseInt(s) < 9)
							{
								x = thisNode.getElement(i).getX() + 8;
								y = thisNode.getElement(i).getY() + 15;
							} else
							{
								x = thisNode.getElement(i).getX() + 5;
								y = thisNode.getElement(i).getY() + 15;
							}
						}
						g2.setColor(Color.black);
						g2.drawString(s, x, y);

					}
				}

			}

			g2.setStroke(new BasicStroke(2f));
			g2.setColor(Color.GRAY.darker());
			for (int i = 0; i < 4; i++)
			{
				if (thisNode.getChild(i) != null
						&& thisNode.getChild(i).getCenter() != null)
				{

					// draws lines from the parent to child nodes
					g2.drawLine(
							// Divide total draw width by (ORDER - 1)
							// (i.e. - the max number of elements spacing links)
							(thisNode.upperLeftX() + i
									* thisNode.getDrawWidth()
									/ (Node234.ORDER - 1)),
							thisNode.upperLeftY() + thisNode.getDrawHeight(),
							(int) thisNode.getChild(i).getCurrentX()
									+ thisNode.getDrawWidth() / 2, thisNode
									.getChild(i).getCurrentY());

					// call to draw child node recursively
					drawStates(g2, thisNode.getChild(i));
				}
			}

		}

	}

}
